package cn.njupt.unionfind;
//对快速合并的优化，不是每次都从左边嫁接到右边，而是从树的高度进行判断
public class Quick_Union_Rank extends Quick_Union{

    int[] height;
    public Quick_Union_Rank(int capacity) {
        super(capacity);
        height=new int[capacity];
        for (int i = 0; i < capacity; i++) {
            height[i]=1;
        }
    }

    @Override
    public void union(int child1, int child2) {
        int p1=find(child1);
        int p2=find(child2);
        if (p1==p2)return;
        if(height[p1]<height[p2]){
            //p1嫁接到p2上
            parent[p1]=p2;
        }else if(height[p1]>height[p2]){
            //p2嫁接到p1上
            parent[p2]=p1;
        }else{ //相等
            parent[p1]=p2;
            height[p2]+=1;
        }
    }
}
